---

deHash.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deHash.hpp
///
/// @brief String, integer, and functor based hash tables
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEHASH_HPP
#define DEHASH_HPP

#include "deGlobalTypes.hpp"
#include "deArray.hpp"

#ifndef NULL
#define NULL (0)
#endif

#pragma warning (disable : 4710)

template <class T>
class deTHashString
{
public:
    class HashNode
    {
    public:
        char * m_IndexString;
        T m_Data;
        HashNode *Prev, *Next;
        deTHashString * m_Hash;

        HashNode(const T & data, const char * s, HashNode * NextNode, deTHashString * Hash)
            : m_Data(data)
        {
            if (s)
            {
                m_IndexString = new char[strlen(s)+1];
                strcpy(m_IndexString, s);
            }
            else
                m_IndexString = NULL;
            Next = NextNode;
            Prev = NULL;
            m_Hash = Hash;
            if (NextNode)
                NextNode->Prev = this;
        }
        ~HashNode()
        {
            if (m_IndexString)
                delete[] m_IndexString;
            if (Prev)
                Prev->Next = Next;
            if (Next)
                Next->Prev = Prev;
        }
    };

    deTHashString(DWORD size)
    : m_Elements(max(size,1)), m_HashSize(max(size,1))
    {
        DWORD i;
        m_ElementNum = 0;
        for (i = 0; i < m_HashSize; i++)
            m_Elements[i] = NULL;
    }
/*  deTHashString(const deTHashString <T> & ref)
    : m_HashSize(ref.m_HashSize)
    {
        m_ElementNum = 0;
    }
*/  ~deTHashString()
    {
        RemoveAllElements();
    }

    DWORD Length()
    {
        return m_ElementNum;
    }
    T * AddElement(const T & element, const char * string)
    {
        DWORD index = HashString(string);
        HashNode * Node = new HashNode(element, string, m_Elements[index], this);
        if (!Node)
            return NULL;
        m_Elements[index] = Node;
        m_ElementNum++;
        return &(Node->m_Data);
    }
    T * FindElement(const char * string, DWORD * Index = NULL) const
    {
        HashNode * p;
        return FindElement(string, p, Index);
    }
    deBoolean RemoveElement(const char * string)
    {
        HashNode * Node;
        DWORD index;
        FindElement(string, Node, &index);
        if (Node && Node->m_Hash == this)
        {
            if (Node->Prev == NULL)
                m_Elements[index] = Node->Next;
            else
                Node->Prev->Next = Node->Next;
            delete Node;
            m_ElementNum--;
            return deTRUE;
        }
        return deFALSE;
    }
    void GetAllElements(deTArray <T*> &array)
    {
        DWORD i, j=0;
        HashNode * Node;
        array.Resize(m_ElementNum);
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                array[j] = &(Node->m_Data);
                j++;
                Node = Node->Next;
            }
        }
    }
    void RemoveAllElements()
    {
        DWORD i, j=0;
        HashNode *Node, *Node2;
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                Node2 = Node->Next;
                delete Node;
                Node = Node2;
                j++;
            }
            m_Elements[i] = NULL;
        }
        m_ElementNum = 0;
    }
    void operator=(const deTHashString <T> &ref)
    {
        throw "don't copy me";
        if (&ref == NULL)
            return;
    }
    T * operator[](const char * string)
    {
        HashNode * p;
        return FindElement(string, p, NULL);
    }
    
private:
    T * FindElement(const char * string, HashNode *&Node, DWORD * Index) const
    {
        DWORD index = HashString(string);
        if (Index)
            *Index = index;
        Node = m_Elements[index];
        while (Node)
        {
            if (!strcmp(Node->m_IndexString, string))
                return &(Node->m_Data);
            Node = Node->Next;
        }
        return NULL;
    }
    DWORD HashString(const char * string) const
    {
        DWORD i, length;
        if (string == NULL)
            return 0;
        for (i = 0; string[i]; i++);
        length = (i > 255) ? 255 : i;
        unsigned long * dword = (unsigned long *)string, total = 0;
        for (i = 0; i < length/4; i++)
        {
            total += *dword;
            dword++;
        }
        i *= 4;
        for (; i < length; i++)
            total += string[i];
        return total % m_HashSize;
    }
    DWORD m_ElementNum;
    const DWORD m_HashSize;
    deTArray <HashNode*> m_Elements;
};

template <class T>
class deTHashInt
{
private:
    class HashNode
    {
    public:
        T m_Data;
        DWORD m_IndexInt;
        HashNode *Prev, *Next;
    #ifdef _DEBUG
        deTHashInt * m_Hash;

        HashNode(const T & data, DWORD i, HashNode * NextNode, deTHashInt * Hash)
            : m_Data(data)
        {
            m_IndexInt = i;
            Next = NextNode;
            Prev = NULL;
            m_Hash = Hash;
            if (NextNode)
                NextNode->Prev = this;
        }
    #else
        HashNode(const T & data, DWORD i, HashNode * NextNode)
        {
            m_Data = data;
            m_IndexInt = i;
            Next = NextNode;
            Prev = NULL;
            if (NextNode)
                NextNode->Prev = this;
        }
    #endif
        ~HashNode()
        {
            m_IndexInt = 0;
            if (Prev)
                Prev->Next = Next;
            if (Next)
                Next->Prev = Prev;
        }
    };
public:
    class iterator
    {
    private:
        deTHashInt<T>* mHash;
        long mIndex;
        HashNode* mNode;
    protected:
        friend class deTHashInt<T>;
        iterator(deTHashInt<T>* hash, DWORD index, HashNode* node)
            : mHash(hash), mIndex(index), mNode(node) {}
        void operator++()
        {   
            mNode = mNode->Next;
            while (mNode == NULL)
            {   ++mIndex;
            if (mIndex >= mHash->m_Elements.size())
                break;
            mNode = mHash->m_Elements[mIndex];
            }
        }
    public:
        iterator() : mHash(NULL), mIndex(0), mNode(NULL) {}
        iterator(const iterator& ref) : mHash(ref.mHash), mIndex(ref.mIndex), mNode(ref.mNode) {}
        T& operator*() const
        {
            DE_ASSERT (mNode != 0);
            return mNode->m_Data;
        }
        T* operator->() const { return &operator*(); }
        bool operator==(const iterator & other) const
        { return (mIndex == other.mIndex) && (mNode == other.mNode); }
        bool operator!=(const iterator & other) const
        { return (mIndex != other.mIndex) || (mNode != other.mNode); }
    };

    deTHashInt(DWORD size)
    : m_Elements(max(size,1)), m_HashSize(max(size,1))
    {
        DWORD i;
        m_ElementNum = 0;
        for (i = 0; i < m_HashSize; i++)
            m_Elements[i] = NULL;
    }
/*  deTHashInt(const deTHashInt <T> & ref)
    : m_HashSize(ref.m_HashSize)
    {
        m_ElementNum = 0;
    }
*/  ~deTHashInt()
    {
        RemoveAllElements();
    }

    DWORD Length()
    {
        return m_ElementNum;
    }
    T * AddElement(const T & element, DWORD Int)
    {
        DWORD index = HashInt(Int);
        HashNode * Node;
    #ifdef _DEBUG
            Node = new HashNode(element, Int, m_Elements[index], this);
    #else
            Node = new HashNode(element, Int, m_Elements[index]);
    #endif
        if (!Node)
            return NULL;
        m_Elements[index] = Node;
        m_ElementNum++;
        return &(Node->m_Data);
    }
    T * FindElement(DWORD Int, DWORD * Index = NULL) const
    {
        HashNode * p;
        return FindElement(Int, p, Index);
    }
    deBoolean RemoveElement(DWORD Int)
    {
        HashNode * Node;
        DWORD index;
        FindElement(Int, Node, &index);
    #ifdef _DEBUG
        if (Node->m_Hash != this)
            return deFALSE;
    #endif
        if (Node)
        {
            if (Node->Prev == NULL)
                m_Elements[index] = Node->Next;
            else
                Node->Prev->Next = Node->Next;
            delete Node;
            m_ElementNum--;
            return deTRUE;
        }
        return deFALSE;
    }
    void GetAllElements(deTArray <T*> &array)
    {
        DWORD i, j=0;
        HashNode * Node;
        array.Resize(m_ElementNum);
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                array[j] = &(Node->m_Data);
                j++;
                Node = Node->Next;
            }
        }
    }
    void RemoveAllElements()
    {
        DWORD i, j=0;
        HashNode *Node, *Node2;
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                Node2 = Node->Next;
                delete Node;
                Node = Node2;
                j++;
            }
            m_Elements[i] = NULL;
        }
        m_ElementNum = 0;
    }

    void operator=(const deTHashInt <T> &ref)
    {
        if (&ref || !&ref)
            throw "don't copy me";
    }
    T * operator[](DWORD Int) const
    {
        void * p;
        return FindElement(Int, p, NULL);
    }


    iterator find(DWORD key)
    {
        DWORD index = HashInt(key);
        HashNode* Node;
        Node = m_Elements[index];
        while (Node)
        {
            if (Node->m_IndexInt == key)
                return iterator(this, index, Node);
            Node = Node->Next;
        }
        return end();
    }
    iterator erase(iterator & entry)
    {
        iterator next = entry;
        ++next;
        HashNode* current = entry.mNode;
        if (current->Prev)
            current->Prev->Next = current->Next;
        else
            m_Elements[entry.mIndex] = current->Next;
        if (current->Next)
            current->Next->Prev = current->Prev;
        delete current;
        return next;
    }
    iterator begin()
    {
        iterator first(this, -1, NULL);
        ++first;
        return first;
    }
    iterator end()
    {
        return iterator(this, m_Elements.size(), NULL);
    }
    
    
private:
    T * FindElement(DWORD Int, HashNode *&Node, DWORD * Index = NULL) const
    {
        DWORD index = HashInt(Int);
        if (Index)
            *Index = index;
        Node = m_Elements[index];
        while (Node)
        {
            if (Node->m_IndexInt == Int)
                return &(Node->m_Data);
            Node = Node->Next;
        }
        return NULL;
    }
    DWORD HashInt(DWORD Int) const
    {
        return Int % m_HashSize;
    }
    DWORD m_ElementNum;
    const DWORD m_HashSize;
    deTArray <HashNode*> m_Elements;
    friend class deTHashInt<T>::iterator;
};

template <class T, class K> // T is data stored, K is key
class deTHashFunctor
{
public:
/*
    class HashExample // for use in a deTHashFunctor object
    {
    u32 m_Value;
    public:
    inline HashExample(u16 index1, u16 index2)
    {
        m_Value = index1 | (index2<<16);
    }
    inline u32 Hash() const
    {
        return m_Value;
    }
    };
*/
    class HashNode
    {
    public:
        T m_Data;
        K m_Key;
        DWORD m_HashValue;
        HashNode *Prev, *Next;
    #ifdef _DEBUG
        deTHashFunctor * m_Hash;

        HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode, deTHashFunctor * Hash)
            : m_Data(data), m_Key(key)
        {
            m_HashValue = hash;
            Next = NextNode;
            Prev = NULL;
            m_Hash = Hash;
            if (NextNode)
                NextNode->Prev = this;
        }
    #else
        HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode)
            : m_Data(data), m_Key(key)
        {
            m_HashValue = hash;
            Next = NextNode;
            Prev = NULL;
            if (NextNode)
                NextNode->Prev = this;
        }
    #endif
        ~HashNode()
        {
        #ifdef _DEBUG
            m_HashValue = 0;
        #endif
            if (Prev)
                Prev->Next = Next;
            if (Next)
                Next->Prev = Prev;
        }
    };

    deTHashFunctor(const DWORD size)
    : m_Elements(max(size,1)), m_HashSize(max(size,1))
    {
        DWORD i;
        m_ElementNum = 0;
        for (i = 0; i < m_HashSize; i++)
            m_Elements[i] = NULL;
    }
/*  deTHashFunctor(const deTHashInt <T> & ref)
    : m_HashSize(ref.m_HashSize)
    {
        m_ElementNum = 0;
    }
*/  ~deTHashFunctor()
    {
        RemoveAllElements();
    }

    DWORD Length()
    {
        return m_ElementNum;
    }
    T * AddElement(const T & element, const K & key)
    {
        DWORD hash = key.Hash(), index = hash%m_HashSize;
        HashNode * Node;
    #ifdef _DEBUG
            Node = new HashNode(element, key, hash, m_Elements[index], this);
    #else
            Node = new HashNode(element, key, hash, m_Elements[index]);
    #endif
        if (!Node)
            return NULL;
        m_Elements[index] = Node;
        m_ElementNum++;
        return &(Node->m_Data);
    }
    T * FindElement(const K & key, DWORD * Index = NULL) const
    {
        HashNode * p;
        return FindElement(key, p, Index);
    }
    deBoolean RemoveElement(const K & key)
    {
        HashNode * Node;
        DWORD index,hashval;
        FindElement(key, Node, &index, &hashval);
    #ifdef _DEBUG
        if (Node->m_Hash != this)
            return deFALSE;
    #endif
        if (Node)
        {
            if (Node->Prev == NULL)
                m_Elements[index] = Node->Next;
            else
                Node->Prev->Next = Node->Next;
            delete Node;
            m_ElementNum--;
            return deTRUE;
        }
        return deFALSE;
    }
    void GetAllElements(deTArray <T*> &array)
    {
        DWORD i, j=0;
        HashNode * Node;
        array.Resize(m_ElementNum);
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                array[j] = &(Node->m_Data);
                j++;
                Node = Node->Next;
            }
        }
    }
    void RemoveAllElements()
    {
        DWORD i, j=0;
        HashNode *Node, *Node2;
        for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
        {
            Node = m_Elements[i];
            while (Node)
            {
                Node2 = Node->Next;
                delete Node;
                Node = Node2;
                j++;
            }
            m_Elements[i] = NULL;
        }
        m_ElementNum = 0;
    }

    void operator=(const deTHashFunctor <T,K> &ref)
    {
        if (&ref || !&ref)
            throw "don't copy me";
    }
    T * operator[](const K & key)
    {
        void * p;
        return FindElement(key, p, NULL);
    }
    
    
private:
    T * FindElement(const K & key, HashNode *&Node, DWORD * Index = NULL, DWORD *HashVal = NULL) const
    {
        DWORD HashValue = key.Hash();
        DWORD index = HashValue % m_HashSize;
        if (Index)
            *Index = index;
        if (HashVal)
            *HashVal = HashValue;
        Node = m_Elements[index];
        while (Node)
        {
            if (Node->m_Key == key)
                return &(Node->m_Data);
            
            Node = Node->Next;
        }
        return NULL;
    }
    DWORD m_ElementNum;
    const DWORD m_HashSize;
    deTArray <HashNode*> m_Elements;
};

//#pragma warning (default : 4710)

#endif

---